МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний університет “Львівська політехніка”
РЕКУРСИВНІ ФУНКЦІЇ, ВКАЗІВНИКИ НА ФУНКЦІЇ В АЛГОРИТМІЧНІЙ МОВІ С Методичні вказівки до лабораторної роботи № 8 з курсу “Проблемно-орієнтовані мови програмування” для базового напрямку “Комп’ютерні науки” Затверджено на засіданні кафедри систем автоматизованого проектування Протокол № _1_ від 22.08.2011 р. ЛЬВІВ – 2011 1. МЕТА РОБОТИ Мета роботи – поглиблене вивчення можливостей функцій з використанням рекурсії та вказівників. 2. ТЕОРЕТИЧНІ ВІДОМОСТІ 2.1. Рекурсивні функції Рекурсивним називається такий спосіб реалізації функції., коли функція може звертатися сама до себе. У рекурсивній функції повинні виконуватися наступні правила: - при кожному виклику такої функції в неї повинні передаватися модифіковані дані; - на якомусь етапі повинен бути припинений подальший виклик даної функції. Рекурсивний процес повинен крок за кроком так спрощувати завдання, щоб зрештою для нього з'явилося не рекурсивне рішення. Тут легко припуститися помилки, що полягає в тім, що функція буде послідовно викликати саму себе нескінченно довго; після завершення кожного виклику рекурсивної функції в точку повернення повинен передаватися деякий результат для подальшого використання. /* Приклад: використання рекурсивної функції. Припустимо, що задано два числа a і b. Необхідно більше із цих чисел розділити на менше. */ #include <iostream.h> void main (void) { float a, b; float recurs (float, float) ; cout <<”Введіть значення a і b " << endl; cin >> a >> b // Ввід значень cout << " a= " << a << " b = " << b; cout << " Результат ділення: " << recurs (a, b); // Прототип функції float recurs (float a, float b) / * Рекурсивна функція */ if(a<b) return recurs(b,a); /* Якщо а < b, те параметри міняються /*місцями (рекурсивний виклик) */ else return a/b; /* Вихід з рекурсії */ } У функцію recurs передаються значення двох дійсних чисел. Припустимо спочатку, що умова а < b не виконується. У цьому випадку при першому ж звертанні до recurs має місце нерекурсивний вихід. Нехай тепер умова а < b виконується. Тоді функція recurs звертається до самої себе, однак параметри а і b у виклику міняються місцями, тобто параметру а у функції передається більше значення (b), а параметру b - менше значення (a). Після чого відбувається вихід з рекурсій і в main буде переданий результат. Рекурсія нерідко входить у визначення математичних алгоритмів. // Приклад: обчислення факторіала за допомогою рекурсії: // #jinclude <iostream.h> void main (void) long fact (int.); /* Прототип функції */ int n; cout << "Введіть n" << endl; cin >> n; /* Ввід значення */ cout << " Факторіал " << n << “ = “ << fact (n); } long fact (int n) /* Рекурсивна функція */ { return (n) ? (long) n * fact(n-1):1; } Розглянемо процес виконання цієї програми. Функція main викликає функцію fact і передає параметр n Якщо n == 0, то повернеться значення 1. Інакше функція fact(n) повинна викликати fact( n-l). Так буде тривати до виклику fact(0), що поверне значення 1 у точку виклику fact(l). Покажемо порядок виконання кожного виклику функції fact і кожного оператора return. Порядок викликів: Порядок повернень:  fact (n) return{1)  fact ( n-l) return(1*0!)  . . .   fact (l) return (( n-l)*( n-2) !)  fact (0) return(n*( n-l)!)   Для розуміння механізму виконання рекурсивної функції запишемо її в такий спосіб: long fact ( int n ) { if (n) return (long) n * fact ( n-1); // IP* else return 1; } Слово else можна й опустити. Розглянемо стан стека у випадку обчислення 3! Головний модуль (main) запише в стек число 3 і адресу повернення (позначимо його IP main) для продовження виконання програми, тобто повернення в точку виклику - у функцію cout << "Факторіал" << n << "=" << fact(n); - для виводу результату. При кожному наступному виклику функції (long) n * fact ( n-1) обчислення даного виразу залишається незавершеним, у стек послідовно записуються ч...